package com.lisp.algorithm.book.c15;

public class LongestCommonSequence_bottomUp {

	public static void main(String[] args) {
		String s1 = "abceda";
		String s2 = "dkanea";
		System.out.println(longestCommonSequence(s1, s2));
	}
	
	public static int longestCommonSequence(String s1, String s2) {
		int s1Len = s1.length(), s2Len = s2.length();
		int subSolution[][] = new int[s1Len+1][s2Len+1];
		int choices[][] = new int[s1Len][s2Len];
		for(int i=0; i<s1Len+1; i++) {
			for(int j=0; j<s2Len+1; j++) {
				if(i == 0 || j == 0) {
					subSolution[i][j] = 0;
				} else {
					int solution = longestCommonSequence(s1.toCharArray(), i, s2.toCharArray(), j, subSolution, choices);
					subSolution[i][j] = solution;
					System.out.println(String.format("subSolution[%s][%s] = %s", i, j, solution));
				}
			}
		}
		printPath(subSolution, choices, s1, s2);
		return subSolution[s1Len][s2Len];
	}
	
	private static void printPath(int[][] solutions, int[][] choices, String s1, String s2) {
		int i = s1.length(), j = s2.length();
		while(solutions[i][j] > 0) {
			int choice = choices[i-1][j-1];
			if(choice == 1) {
				i = i-1;
				j = j-1;
				System.out.println(String.format("s1=%s, s2=%s", s1.subSequence(0, i), s2.subSequence(0, j)));
			} else if(choice == 2) {
				
				j = j-1;
				System.out.println(String.format("s1=%s, s2=%s", s1.subSequence(0, i), s2.subSequence(0, j)));
			} else {
				i = i-1;
				System.out.println(String.format("s1=%s, s2=%s", s1.subSequence(0, i), s2.subSequence(0, j)));
			}
		}
	}

	private static int longestCommonSequence(char a[], int aEnd, 
			char b[], int bEnd, int[][] subSolution, int[][] choices) {
		
		if(a[aEnd-1] == b[bEnd-1]) {
			choices[aEnd-1][bEnd-1] = 1;
			return  1 + subSolution[aEnd-1][bEnd-1];
		} else {
			int x = subSolution[aEnd][bEnd-1];
			int y = subSolution[aEnd-1][bEnd];
			if(x > y) {
				choices[aEnd-1][bEnd-1] = 2;
				return x;
			} else {
				choices[aEnd-1][bEnd-1] = 3;
				return y;
			}
		}
	}
}
